1. Field of the Invention
The invention relates to a receiving device used for transmitting digital data in satellite communications, mobile communications, and mobile satellite communications. More particularly, the invention relates to a digital data demodulating device using a viterbi algorithm for determining the transmission data.
2. Description of the Related Art
It is well known that, in a receiving device, a viterbi algorithm is very effective when a channel includes an ISI (Inter-symbol Interference) as a device for deciding the data from a transmitted received signal which has been digitally modulated using methods such as PSK (Phase Shift Keying). A conventional digital data demodulating device is discussed below using an example disclosed in "The Viterbi Algorithm" written by G. D. Forney, Jr. (Proc. IEEE, Vol. 61, No. 3, pp. 268-278, March 1973).
FIG. 18 illustrates a model of a channel having ISI. Transmission data S61, which has been modulated in BPSK (Binary Phase Shift Keying), are sequentially input to the shift register 61, which contains (V-1) stages, where, (V-1) is the number of multi-path wave maximum delay symbols that are contained in the received signal. The transmission data S61 and the output from the shift register 61 are multiplied by tap coefficients (CIR) C.sub.1, . . . , C.sub.V, respectively, where CIR represents the channel impulse response. The resulting products are added in an adder 63. The output from the adder 63 is added to the noise w.sub.n in an adder 64, and the adder 64 outputs a received signal S62. The received signal S62 is expressed by the following formula (1), where received signal S62 is denoted as I.sub.n, the transmission signal S61 as I.sub.n, and the respective outputs from the shift register 61 as I.sub.n-1', I.sub.n-2', . . . , I.sub.n-(V-1). ##EQU1##
In the channel model having the ISI illustrated in FIG. 18, the reception data is determined based not only on current transmission data, but also on past transmission data. Therefore, it is necessary to take the past transmission data into account in deciding the current transmission data.
The past transmission data is stored in the shift register 61. If the shift register length is (V-1) as illustrated in FIG. 18, the past transmission data of (V-1) symbol period is stored in the shift register 61. The past transmission data is stored in pairs in the shift register, and these pairs are defined as "states". If the shift register length is 2 (V=3), the following four states are included: state [0, 0], state [0, 1], state [1, 0] and state [1, 1]. In order to simplify the explanation, it is assumed here that the transmission data contain only two numbers, 0 and 1. In this case, the number of the states, N.sub.s, are expressed by the formula N.sub.s =2.sup.V-1.
A trellis diagram illustrates state variation which occurs as time passes. FIG. 19 is a trellis diagram illustrating the state variation when the shift register length is 2(V=3)s. In this case, the state [0, 0] is denoted as state A, the state [0, 1] as state B, the state [1, 0] as state C and the state [1, 1] as state D. In FIG. 19, the states A, B, C and D are illustrated in the vertical direction from the top to the bottom, and the time n-1, n, n+1, n+2, n+3 and n+4 are illustrated in the horizontal direction from the left to the right. A line is drawn from each state (each state is represented as a circle) to two other states at the subsequent time. These lines represent the transition of the states according to time. For instance, two lines are drawn from the state A to the state A and the state C of the subsequent time. The line drawn from the state A to the state A of the subsequent time illustrates a state transition when the input data (current transmission data) is 0. The line drawn from the state A to the state C of the subsequent time illustrates a state transition when the input data is 1.
These lines in the trellis diagram are called "branches". Here, a state at time n is represented as S., and the branches extending from the time n-1 to the time n are represented as S.sub.n- 1/S.sub.n. As time proceeds, the states change via branches. The track of a state is defined as a path. In FIG. 19, examples of paths are illustrated with bold lines. A path starting at time n-1 and ending at time n+4 is represented as S.sub.n-1 /S.sub.n / . . . /S.sub.n+4. Paths determine how states change, at the same time, determine the transmission data sequence I.sub.n, I.sub.n+2, . . . , I.sub.n+4. Therefore, it is possible to determine the transmission data sequence by determining the path at the receiver's end.
A viterbi algorithm determines a sequence of transmission data using the trellis diagram. FIG. 20 illustrates a conventional digital data demodulating device using a viterbi algorithm. In FIG. 20, a CIR estimating circuit 500 and a viterbi processor 100 receive a signal S1. The CIR estimating circuit estimates CIR based on the input signal S1, and outputs the estimated CIR S2. A replica calculating circuit 200 receives the estimated CIR S2 and calculates a replica S3 of the received signal S1. The viterbi processor 100 receives the signal S1 and the replica S3, determines the transmission data based on the received signal S1 and replica S3 according to the viterbi algorithm, and outputs the decision data S4.
The replica calculating circuit 200 calculates the replica S3 of a received signal S1 using the CIR S2, which has been estimated in the CIR estimating circuit 500. C.sub.1, C.sub.2, . . . , C.sub.V, which represent CIRs for the respective taps V.sub.1, V.sub.2, . . . , V.sub.V, are represented as B.sub.1, B.sub.2, . . . , B.sub.V, which are the estimated CIR S2 output from the CIR estimating circuit 500. As the trellis diagram illustrates, the branch S.sub.n-1 /S.sub.n, which starts at time n-1 and ends at time n, is determined by pairs of the transmission data S61 and the past transmission data which are stored in the shift register 61. That is, assuming that candidate for the transmission data S61 is J.sub.n, and candidates for the past transmission data are J.sub.n-1, J.sub.n-2, . . . , J.sub.n-(v-1), vector (J.sub.n, J.sub.n-1, . . . , J.sub.n-(v-1)) takes 2.sup.V values from (0, 0, . . . , 0) to (1, 1, . . . , 1). Accordingly, the branches S.sub.n-1 /S.sub.n have 2.sup.V ways, which start at time n-1 and end at time n. Accordingly, the replica S3 has 2.sup.V values, corresponding to the respective branches illustrated in the trellis diagram. A replica R.sub.n (k) corresponding to the k-th branch (k=1, 2, . . . , 2.sup.V) are obtained from the following formula (2). ##EQU2##
In formula (2), the vector (J.sub.n, J.sub.n-1, . . . , J.sub.n'(V-1)) takes different 2.sup.V values from (0, 0, . . . , 0) to (1, 1, . . . , 1) corresponding to k.
An example of the viterbi processor 100 is illustrated in FIG. 21. In FIG. 21, the same portions as those shown in FIG. 20 are represented with the same numbers, and repeated explanations of them are omitted. A branch metric generating circuit 110 obtains a respective branch metric corresponding to the respective branches, which are illustrated in the trellis diagram. An ACS processing circuit 120 performs ACS processes (ACS: Add, Compare and Select) based on the branch metric output from the branch metric generating circuit 110. A path metric memory 130 stores the total sum of the branch metric contained in the candidate paths in the past transmission data sequence. A path memory 140 stores the candidate paths in the past transmission data sequence. A decision circuit 150 decides the transmission data based on the output from the path memory 140, and outputs the decision data S4.
The branch metric generating circuit 110 obtains and outputs 2.sup.V different values of branch metric En (k), which correspond to the respective branches, from the 2.sup.V replicas S3 illustrated in the trellis diagram. The branch metric En (k) are expressed in a following formula (3), where the received signal S1 is r.sub.n, and the 2.sup.V replicas S3 are R.sub.n (k). EQU E.sub.n (k)=.vertline.r.sub.n -R.sub.n (k).vertline..sup.2 (k=1, 2, . . . , 2.sup.v) (3)
The ACS processing circuit 120 selects a path to the respective states (represented with white circles) at the respective time. If the number of states is N.sub.S, the ACS processing circuit 120 selects Ns paths corresponding to the respective states. These selected N.sub.S paths are called "surviving paths", and they are stored in the path memory 140. The path memory 140 also stores the candidates of the past transmission data sequence up to time U, which corresponds to the surviving paths. This "U" is defined as path memory length. The total sum of the branch metric included in the surviving paths is called surviving path metric, and is stored in the path metric memory 130. The ACS processing circuit 120 performs the processes on the respective states. Processes corresponding to a state "m" (m=1, 2, . . . , N.sub.S) are explained.
Branch metrics E.sub.n (p) and E.sub.n (q), which correspond to the two branches connected to the state "m", are input to the ACS processing circuit 120 from the branch metric generating circuit 110. Two surviving path metrics PM.sub.n-1 (i) and PM.sub.n-1 (j) corresponding to two states "i" and "j", which are the states connected by the two branches connected to the state "m" and the one period prior state "m", are also input to the ACS processing circuit 120 from the path metric memory 130. Also, two surviving paths PT.sub.n-1 (i), PT.sub.n-1 (j) corresponding to two states "i" and "j", which are the states connected by the two branches connected to the state "m" and the one period prior state "m", are input to the ACS processing circuit 120 from the path memory 140. The branch metrics E.sub.n (p) and E.sub.n (q) are added to the path metrics PM.sub.n-1 (i) and PM.sub.n-1 (j), respectively, then the two sums are compared. The smaller sum is selected as a current surviving path metric PM.sub.n (m) corresponding to the state "m". In other words, the current surviving path metric PM.sub.n (m) are expressed by the following formula (4). EQU PM.sub.n (m)=min{E.sub.n (p)+PM.sub.n-1 (i), E.sub.n (q)+PM.sub.n-1 (j)} (4)
The updated surviving path metric PM.sub.n (m) is stored in the path metric memory 130. If E.sub.n (p)+PM.sub.n-1 (i) are smaller in the comparison between E.sub.n (p)+PM.sub.n-1 (i) and E.sub.n (q)+PM.sub.n-1 (j) explained above, PT.sub.n-1 (i) are selected. If E.sub.n (q)+PM.sub.n-1 (j) are smaller, PT.sub.n-1 (j) are selected The oldest transmission data candidate is removed from this selected surviving path which is the one period prior state "m", and current transmission data candidate which is determined in the path selected based on the comparison result is added to produce the current surviving path PT.sub.n (m), which corresponds to the state "m". The updated current surviving path PT.sub.n (m) is stored in the path memory 140.
The decision circuit 150 decides only the oldest transmission data candidate in the surviving path corresponding to a fixed state, as decision data, of all the surviving paths corresponding to the respective states stored in the path memory 140, and outputs the transmission data candidate as decision data S4.
As explained above, the conventional digital data demodulating device decides the sequence of transmission data from the replica of the received signal, which is calculated using the CIR estimated in the CIR estimating circuit, and received signal based on the trellis diagram.
However, in a conventional digital data demodulating device, as a bit rate of transmission increases, the delay dispersion of the multi-path wave contained in the received signal also increases. As a result, the circuit scale of the digital data demodulating device becomes large, and more operations are necessary. Particularly, the circuit scale of the replica calculating portion increases exponentially in relation to the delay dispersion of the multi-path wave.